The present invention relates generally to a method and apparatus for software development tools and is directed more particularly to a generational garbage collection tool of a compiler system in a computer system.
Compiler systems operating in a computer system may manage allocation of computer resources such as computer memory at compile-time or at run-time. One method of computer resource allocation is garbage collection which is the automatic management of dynamically allocated computer resources, or storage. By the technique of garbage collection computer resources occupied by data objects are reclaimed when the data object may not be accessed again by an executing program. The reclaimed data object is referred to herein as xe2x80x9cgarbage.xe2x80x9d It would be advantageous for garbage collection to accurately and effectively operate in a threaded environment and with objects that are referenced by interior as well as exterior pointers.
The term xe2x80x9ccompile-timexe2x80x9d refers to the period of compilation before a computer program is loaded and executing on the computer system, and the term xe2x80x9crun-timexe2x80x9d refers to the period of compilation after the computer program is loaded and is able to execute on the computer system. The term xe2x80x9cstoragexe2x80x9d refers herein to computer resources such as memory, and may be data or instructions used in executing a computer program.
A live object may be globally known. That is, procedures other than the one that created the object may access the object. Therefore, a garbage collector includes bookkeeping techniques to determine at run-time when an object is no longer live relative to any program that may attempt to access the object and this state is referred to herein as an object being xe2x80x9cdead.xe2x80x9d This bookkeeping method may include a determination of a safe point of the program. The safe point therefore is a point during program execution where the execution of the objects of a program may be halted and garbage collection may be safely performed. That is, at a safe point the garbage collector may safely dispose of all unresolved pointers and program code related to a dead object without impairing the functionality of the programs when garbage collection has completed and the programs are executing again.
Live objects, and not garbage, are preserved by a garbage collector thereby ensuring that pointers are not directed at dead, deallocated objects. Further, the efficiency of access to live objects may be improved during garbage collection by relocating the objects to contiguous storage locations. Therefore, after relocation of a live object, and since there may be more than one pointer referencing the object, garbage collection may work with threading techniques to ensure that the relationship between all the pointers referencing the object is maintained while only updating one pointer. That is, the pointers may be threaded thereby requiring update of only one pointer after object relocation.
Garbage collectors have been inhibited by the problem of reclaiming system resources in a multi-threaded programming environment. It will be appreciated that the term xe2x80x9cthreadxe2x80x9d refers to a linear control flow of an executing program, and in a multi-threaded environment, several execution paths in an executing program may be executing simultaneously. Recall that a garbage collector requires access to system resources to relocate objects. Therefore, when several threads are being executed, including a garbage collector thread and another thread, both threads may be halted if they are simultaneously attempting to access the same system resources. Since system resources typically may be allocated in a serial fashion, the simultaneous attempts to obtain system resources will not be satisfied and the program may be indefinitely halted in a deadlocked state.
Further, current garbage collectors have been inhibited by the problem of locating a true safe point. For instance, it has not been possible to accurately determine during run-time the safe point of programs with interior pointers, especially in a multi-threaded environment. It will be appreciated that interior pointers may traverse unpredictable paths and therefore make identification of live or dead objects difficult. Accordingly there is a need to improve garbage collection to enable safe access to interior pointers in thread-based programs.
An embodiment of the present invention includes a generational garbage collection tool and method for a computer system that pre-allocates computer resources during compile-time for later use by a generational garbage collector at run-time. A purpose of generational garbage collection is to reduce the overall cost of dealing with long-lived objects and thereby allow a generational garbage collector to focus deallocation efforts on young objects, which are more likely to be dead. Another purpose of generational garbage collection is to reduce pause time to a level that does not disturb interactive users. The term xe2x80x9cpause timexe2x80x9d refers herein to the time a program is halted due to garbage collection. The technique of generational garbage collection achieves both purposes by segregating objects by age, and by collecting older generations much less frequently than younger ones. Therefore, improving the efficiency and expanding the scope of generational garbage collection will improve the management and allocation of computer resources. The terms xe2x80x9cgarbage collectorxe2x80x9d and xe2x80x9cgenerational garbage collectorxe2x80x9d will be used interchangeably herein.
Fundamental concepts of generational garbage collection are explained in, xe2x80x9cUnprocessed Garbage Collection Techniques,xe2x80x9d by Paul R. Wilson. Also, garbage collection is explained in xe2x80x9cGarbage Collection Algorithms for Automatic Dynamic Memory Management,xe2x80x9d by Richard Jones and Rafael Lins, 1996, John Wiley and Sons.
When an object is threaded and a pointer that references the object is interior, accurate allocation of space to facilitate run-time generational garbage collection is very difficult. Therefore, it is an object of the invention to allocate space for interior pointers at compile-time when the location of interior pointers is known and thereby facilitate generational garbage collection. By enabling the use of threaded pointers that reference objects for generational garbage collection, the resource savings of threads may be employed. More particularly, by enabling the use of threaded interior pointers during generational garbage collection, live object relocation is improved by requiring an update to one pointer instead of updating each pointer that references an object.
It will be appreciated that the terms xe2x80x9cinstructions,xe2x80x9d xe2x80x9cdata structures,xe2x80x9d and xe2x80x9cdataxe2x80x9d may refer to values such as integer, real, or complex numbers; or characters. Alternatively, the values may be pointers that reference values. Therefore, a pointer provides direction to locate a referenced value. The term xe2x80x9cinterior pointerxe2x80x9d refers to a pointer to a location within a program other than the starting point for the program execution. The term xe2x80x9cobjectxe2x80x9d refers herein to a structured data record that may include instructions that operate and execute in association with the compilation system. Further an object may include instructions at locations that may be referenced by pointers. It will be appreciated that objects may include encapsulation and inheritance features such as are used in object-oriented programming. Those skilled in the art will appreciate these techniques used in object-oriented programming.
It is another object of the invention to efficiently manage at compile-time the bookkeeping necessary to allocate storage to pointers for use during generational garbage collection. That is the present embodiment identifies the pointers that may be updated due to generational garbage collection, and by selectively allocating space to those pointers that may be accessed during generational garbage collection and not all pointers, computer resources are saved. More particularly, with reference to interior pointers the present embodiment allocates space at compile-time to hold offset information used to locate the initial address of an object. The term xe2x80x9coffsetxe2x80x9d refers herein to a representation of the distance between the initial, first address location of the object and the location of data actually referenced. It will be appreciated that use of an offset allows interior pointers to reference the starting address of the object without reference to the actual location of the starting address. Further, with reference to exterior pointers, the present embodiment allocates space at compile-time to identify the pointer as exterior.
It is also an object of the invention to facilitate the location of a true safe point by accurately identifying interior pointers and allocating space for generational garbage collection at compile-time. Therefore, safe relocation of interior pointers is enabled and proper operation of the program after generational garbage collection is ensured.
It is also an object of the invention to ensure that during run-time a single update to an object is attempted at a time. Therefore, the present invention may include locking information in the pointer to determine whether the object is presently being updated and is therefore locked.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.